2D barcodes derive their name from the traditional 1D barcodes, consisting of a set of vertical bars or stripes of varying widths and spacing. 2D barcodes, on the contrary, consist of 2D arrays of rectangles or dots. The most commonly used 2D symbologies are the so-called Data Matrix, QR Code, and PDF417—all of them employing Reed-Solomon error correction code.
2D barcodes, designed to carry certain information about products on which they are used, have become an important component in counterfeiting and anti-counterfeiting efforts. “Track and trace” through an “information” label is a main application for the barcode industry. Upgrading this “information” barcode with protective, anti-counterfeiting features is a natural extension—from tracking an individual item throughout the value chain with a barcode to using that same system and that same barcode to ensure that all products within the value chain are authentic. Protecting labels that are already circulating in the supply chain, instead of building separate product protection systems, makes this approach very cost effective.
Accordingly, there is a need in Auto ID (Automatic Identification and Data Capture) industry for barcode authentication technology to combat counterfeiting and to protect product integrity employing the existing barcode information infrastructure.
One of the widely used concepts of data authentication is the concept of digital signature. A digital signature scheme allows one to sign an electronic message and later the produced signature can be validated by the owner of the message or by any verifier. This concept employs asymmetric cryptography and is covered by a number of international and domestic standards. These include for example ISO/IEC 14888 and ISO/IEC 9796, which specify digital signature mechanisms with appendix and with message recovery, respectively. Additionally, DSS (Digital Signature Standard), issued by the National Institute of Standards and Technology (NIST), specifies a suite of algorithms which can be used to generate a digital signature.
A digital signature is computed using a set of rules and a set of parameters such that the identity of the signatory and integrity of the data can be verified. An algorithm provides the capability to generate and verify signatures. Signature generation makes use of a private key to generate a digital signature. Signature verification makes use of a public key which corresponds to, but is not the same as, the private key.
Because asymmetric key algorithms are nearly always very computationally intensive direct use of this concept for barcode applications is not practical or even feasible. In most “field” applications, the barcode decoding algorithm is embedded into the digital signal processing (“DSP”) platform (for example, a scanner), having limited computational resources. Running cryptographical software on such devices would make decoding processes slow if not impossible.
In addition, digital signature mechanisms with appendix generate a message authentication code (“MAC”, sometimes called a tag) to the message to be authenticated, effectively increasing the length of the message and, as a result, the size of the encoded symbol. This creates a problem for applications where the space for the symbol is limited, particularly for DPM (Direct Part Marking) applications. A hash function is used in this process to obtain a MAC tag.
Furthermore, utilizing cryptographical software in addition to the encoding/decoding software, makes the combined product more expensive and substantially more difficult to deploy. It would be preferable to build an authentication mechanism into an existing encoding/decoding algorithm as an optional “security feature”.